package ltd.smallwang;

/**
 * @author justd
 * @date 2024-10-01 20:30
 */
public class Leetcode0045 {

  public int jump(int[] nums) {
    int len = nums.length;
    if (len == 1) {
      return 0;
    }
    int[] recordArr = new int[len];
    recordArr[0] = 0;
    int curr = 0;
    for (int i = 0; i < len; i++) {
      if (i + nums[i] > curr) {
        setStep(recordArr, curr + 1, i + nums[i], recordArr[i] + 1);
        curr = i + nums[i];
      }
    }
    return recordArr[len - 1];
  }

  private void setStep(int[] recordArr, int begin, int end, int step) {
    for (int i = begin; i <= end && i < recordArr.length; i++) {
      recordArr[i] = step;
    }
  }
}
